C. Boring Day
Egor 有一副
埃戈尔对纸牌的顺序了如指掌。请帮助 Egor 确定他在这样的游戏中最多可以赢多少轮。请注意,伊戈尔不需要连续赢几轮。
我发现这种思想(双指针/简单 DP 思想)我基本每次都想不到... 多练吧
贪心:双指针
#define int long long
void solve() {
int n, l, r;cin >> n >> l >> r;
vector<int> a(n);
for (int i = 0;i < n;i++)cin >> a[i];
int ans = 0, cur = 0, L = 0, R = 0;
while (L < n) {
while (R < n && cur < l) {
cur += a[R];R++;
}
if (l <= cur && cur <= r) {
ans++;L = R;cur = 0;
} else {
cur -= a[L];L++;
}
}
cout << ans << '\n';
}
DP
#define int long long
void solve() {
int n, l, r;cin >> n >> l >> r;
vector<int> a(n);
for (int i = 0;i < n;i++)cin >> a[i];
vector<int> dp(n + 1);
int s = 0;
int j = -1;
for (int i = 0; i < n; i++) {
dp[i + 1] = max(dp[i + 1], dp[i]);
if (j < i) {
j = i;
s = 0;
}
while (j < n && s < l) {
s += a[j++];
}
if (s >= l && s <= r) {
dp[j] = max(dp[j], dp[i] + 1);
}
s -= a[i];
}
cout << dp[n] << '\n';
}